// 经典递归解法：取出不合法的情况
// 1. left 随时加，不能超过 n
// 2. right 之前必须右左括号 且 左括号个数 大于 右括号个数
// 回溯跳出条件就是左右括号都已经排完的情况
// 括号成对存在，先有左括号再有右括号，所以只有右括号的数量小于左括号的数量才能进行右括号的添加
// 最后如果右括号的数量为 0,表示右括号已经排完了，同时意味着左括号也排完了

var generateParenthesis = function (n) {
  const res = []; // 解集
  const generate = (str, left, right) => {
    if (str.length == 2 * n) {
      // 字符串构建完成
      res.push(str); // 将字符串加入解集
      return; // 结束当前递归（结束当前搜索分支）
    }
    if (left > 0) {
      // 只要左括号有剩，可以选它，继续递归做选择
      generate(str + "(", left - 1, right);
    }
    if (right > left) {
      // 右括号的保有数量大于左括号的保有数量，才能选右括号
      generate(str + ")", left, right - 1);
    }
  };
  generate("", n, n); // 递归的入口，初始字符串是空字符串，初始括号数量都是n
  return res;
};
